package ee.homework.first;

import java.util.Random;

public class Quicksort {

	private static Random random = new Random();

	public void quickSort(int[] array) {
		quickSort(array, 0, array.length - 1);
	}

	private void quickSort(int[] array, int first, int last) {
		if (first < last) {
			int pivot = partition(array, first, last);
			quickSort(array, first, pivot - 1);
			quickSort(array, pivot + 1, last);
		}
	}

	private int partition(int[] array, int first, int last) {
		int x = array[last];
		int index = first - 1;
		for (int j = first; j < last; j++) {
			if (array[j] <= x) {
				index++;
				int tmp = array[j];
				array[j] = array[index];
				array[index] = tmp;
			}
		}
		index++;
		int tmp = array[last];
		array[last] = array[index];
		array[index] = tmp;
		return index;
	}

	public void randomizedQuickSort(int[] array) {
		randomizedQuickSort(array, 0, array.length - 1);
	}

	private void randomizedQuickSort(int[] array, int first, int last) {
		if (first < last) {
			int pivot = randomizedPartition(array, first, last);
			randomizedQuickSort(array, first, pivot - 1);
			randomizedQuickSort(array, pivot + 1, last);
		}
	}

	private int randomizedPartition(int[] array, int first, int last) {
		int i = random.nextInt(last - first) + first;
		int tmp = array[i];
		array[i] = array[last];
		array[last] = tmp;
		return partition(array, first, last);
	}

	public void printList(int[] list) {
		for (int i = 0; i < list.length; i++) {
			System.out.print(list[i] + "  ");
		}
		System.out.println();
	}
}
